import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;


public class FindSum extends ArrayIndexOutOfBoundsException{
	


	public Set<Integer> find2InArray(int[] arr, int sum){
		Set<Integer> find = new HashSet<Integer>();
		Set<Integer> set = new HashSet<Integer>();
		
		for(int i = 0; i<= arr.length-1; i++){
			set.add(arr[i]);
		}
		
		Iterator it = set.iterator();
		while(it.hasNext()){
			int temp = (Integer) it.next();
			int pair = sum - temp;
			if(set.contains(new Integer(pair))&&pair != temp){
				find.add(pair);
				find.add(temp);
			}
		}
		
		return find;
	}

	public int[] TwoSum(int[] arr, int target){
		if(arr.length == 0 || arr == null){
			return null;
		}
		Map<Integer, Integer> hash = new HashMap<Integer, Integer>();
		
		int[] result = new int[2];
		
		for(int i = 0; i < arr.length; i++){
			if(!hash.containsKey(arr[i])){
				hash.put(target - arr[i], i);
				if((target - arr[i]) * 2 == target){
					break;
				}
			}
			
			if(hash.containsKey(arr[i])){
				result[0] = hash.get(arr[i]);
				result[1] = i;
				
			}
		}
		return result;
	}
	
	public HashSet<ArrayList<Integer>> ThreeSum(int[] arr, int sum) {
	    if(arr.length == 0 || arr == null){
	    	return null;
	    }
	    
	    Arrays.sort(arr);
	    HashSet<ArrayList<Integer>> triplets = new HashSet<ArrayList<Integer>>();
	    ArrayList<Integer> triplet = new ArrayList<Integer>();
	    int n = arr.length;
	    for (int i = 0;i < n; i++) {
	        int j = i + 1;
	        int k = n - 1;
	        while (j < k) {
	            int sum_two = arr[i] + arr[j];
	            if (sum_two + arr[k] < sum) {
	                j++;
	            } else if (sum_two + arr[k] > sum) {
	                k--;
	            } else {
	                triplet.add(arr[i]);
	                triplet.add(arr[j]);
	                triplet.add(arr[k]);
	                ArrayList<Integer> temp = (ArrayList<Integer>) triplet.clone();
	                triplets.add(temp);
	                j++;
	                k--;
	                triplet.clear();
	            }
	        }
	    }
	    return triplets;
	}
	
	
	public static void main(String[] args)  {
		int[] arr = {2, 10, 7, 6};
		int sum = 12;
		int[] test = {-1, 0, 1,2,-1, 4};
		FindSum f = new FindSum();
		System.out.println(f.ThreeSum(test, 7).toString());
		Set<Integer> find = f.find2InArray(arr, sum);
		int[] a = f.TwoSum(arr, 12);
		System.out.println(a[0]+ ", " + a[1]);
		System.out.print(find.toString());
		

	}

}
